package com.wtgroup.demo.mianshi.算法.二叉树.遍历;

import com.wtgroup.demo.mianshi.算法.二叉树.model.CompleteBinTree;
import com.wtgroup.demo.mianshi.算法.二叉树.model.Node;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @author dafei
 * @version 0.1
 * @date 2021/3/27 23:09
 */
public class D_后序 {

    public static void main(String[] args) {
        List<Integer> vals = Arrays.asList(1,2,3,4,5,6,7,8);
        CompleteBinTree<Integer> binTree = new CompleteBinTree<Integer>(vals);

        Node<Integer> root = binTree.getRoot();

        m1(root, new ArrayList<>());
        // m2(root);
        System.out.println();
        noRecurvePost(root);
    }

    public static void m1(Node root, ArrayList<Node> result) {
        if (root != null) {
            m1(root.getLeft(), result);
            m1(root.getRight(), result);
            // System.out.print(root.getData() + " ");
            result.add(root);
        }
    }

    // todo 有点复杂, 没搞定
    // public static void m2(Node root) {
    //     Stack<Node> stack = new Stack<>();
    //     Node curNode = root;
    //     while (curNode !=null || !stack.isEmpty()) {
    //         if (curNode != null) {
    //             stack.push(curNode);
    //             curNode = curNode.getLeft();
    //         } else {
    //             Node p = stack.peek();
    //             curNode = p.getRight();
    //             if (curNode==null) {
    //                 System.out.print(p.getData() + " ");
    //                 stack.pop();
    //             }
    //         }
    //     }
    // }

    /**
     * 非递归后序遍历
     *
     * 确保父先进栈2
     *
     * │  left tree  │
     * │  right tree │
     * │   parent    │
     * └─────────────┘
     */
    public static void noRecurvePost(Node head) {
        // 后序
        Stack<Node> s1 = new Stack();
        Stack<Node> s2 = new Stack();
        s1.push(head);
        while(!s1.isEmpty()) {
            Node cur = s1.pop();
            s2.push(cur); // 确保父先进s2
            if(cur.left != null) {
                s1.push(cur.left);
            }
            if(cur.right !=null ) {
                s1.push(cur.right);
            }
        }
        while(!s2.isEmpty()) {
            System.out.print(s2.pop() + " ");
        }
    }
}
